package leetcode.Hot100;

import java.util.*;

/**
 * @author Cheng Jun
 * Description: 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 * <p>
 * 返回所有可能的结果。答案可以按 任意顺序 返回。
 * <p>
 * https://leetcode-cn.com/problems/remove-invalid-parentheses/
 * @version 1.0
 * @date 2021/12/30 21:53
 */
public class removeInvalidParentheses {

    public static void main(String[] args) {
        List<String> strings = removeInvalidParentheses1(")(f");
        System.out.println(strings.get(0));
        System.out.println(strings.get(1));
    }

    // 输入：s = "(a)())()"
    // 输出：["(a())()","(a)()()"]
    // 思路1：从左边优先 匹配，然后再从右边优先匹配
    // 反例： (a)()) + (a)())  其中 “+” 为了方便阅读
    // 因为 (a)() ===》(a()) (a)()， (a()) 表示 1，(a)() 表示2，那么答案应该是 12 11 22 21 (a)( + (a)())，如果按照思路求解的话，只能得到 11, 22
    static public List<String> removeInvalidParentheses(String s) {
        return null;
    }

    // 输入：s = "(a)())()"
    // 输出：["(a())()","(a)()()"]
    // 条件中的 1 <= s.length <= 25，这个25 就很有意思。似乎在表达着用穷举法
    // 删除最小数量的无效括号，说明我们要删除的数量都是相同的.
    // 我们可以一次遍历后找到，要删除的 左括号数量（leftBracketNum）、右括号数量（rightBracketNum）
    // 那么，我们知道了要删除的 leftBracketNum， rightBracketNum
    // 剩下的就 穷举吧，最怕TMD最后给我来个超时
    static public List<String> removeInvalidParentheses1(String s) {
        // 可能的结果集
        Set<String> possibleRes = new HashSet<>();
        Deque<Character> deque = new LinkedList<>();
        // 找到 leftBracketNum，rightBracketNum
        int leftBracketNum = 0;
        int rightBracketNum = 0;
        char[] charArr = s.toCharArray();
        // 左括号下标集合，右括号下标集合
        List<Integer> leftBracketIndexes = new ArrayList<>();
        List<Integer> rightBracketIndexes = new ArrayList<>();
        for (int i = 0; i < charArr.length; i++) {
            char c = charArr[i];
            if (c == '(') {
                deque.addLast(c);
                leftBracketIndexes.add(i);
            }
            if (c == ')') {
                if (deque.peekLast() != null) {
                    deque.removeLast();
                } else {
                    rightBracketNum++;
                }
                rightBracketIndexes.add(i);
            }
        }
        leftBracketNum = deque.size();
        if (leftBracketNum == 0 && rightBracketNum == 0) {
            List<String> list = new ArrayList<>();
            list.add(s);
            return list;
        } else {
            // 获取组合
            getPossibleRes(possibleRes, s, leftBracketNum, leftBracketIndexes, rightBracketNum, rightBracketIndexes);
        }
        // 验证 possibleRes 的 res 是否有效
        removeInValidRes(possibleRes);
        return new ArrayList<>(possibleRes);
    }

    // 1 <= s.length <= 25
    // s 由小写英文字母以及括号 '(' 和 ')' 组成
    // s 中至多含 20 个括号
    static void getPossibleRes(Set<String> possibleResSet, String source,
                               int leftBracketNum, List<Integer> leftBracketIndexes,
                               int rightBracketNum, List<Integer> rightBracketIndexes) {

        // 从 indexList 中选出 bracketNum 个的所有组合
        // source.
        List<List<Integer>> lefIndexList = new ArrayList<>();
        if (leftBracketNum > 0) {
            dfs(leftBracketIndexes.stream().mapToInt(Integer::valueOf).toArray(),
                    leftBracketNum, 0, new ArrayList<>(leftBracketNum), lefIndexList);
        }
        List<List<Integer>> rightIndexList = new ArrayList<>();
        if (rightBracketNum > 0) {
            dfs(rightBracketIndexes.stream().mapToInt(Integer::valueOf).toArray(),
                    rightBracketNum, 0, new ArrayList<>(rightBracketNum), rightIndexList);
        }
        char[] srcChar = source.toCharArray();
        // 左右下标的组合
        List<List<Integer>> indexList = new ArrayList<>();
        if (lefIndexList.isEmpty()) indexList = rightIndexList;
        if (rightIndexList.isEmpty()) indexList = lefIndexList;
        if (!rightIndexList.isEmpty() && !lefIndexList.isEmpty()) {
            for (List<Integer> leftIndexes : lefIndexList) {
                for (List<Integer> rightIndexes : rightIndexList) {
                    List<Integer> indexes = new ArrayList<>();
                    indexes.addAll(leftIndexes);
                    indexes.addAll(rightIndexes);
                    indexList.add(indexes);
                }
            }
        }
        for (List<Integer> indexes : indexList) {
            char[] charTemp = new char[srcChar.length - indexes.size()];
            Set<Integer> indexSet = new HashSet<>(indexes);
            for (int i = 0, k = 0; i < srcChar.length; i++) {
                if (indexSet.contains(i)) {
                    continue;
                } else {
                    if (charTemp.length > k) charTemp[k++] = srcChar[i];
                }
            }
            possibleResSet.add(new String(charTemp));
        }
    }

    static void dfs(int[] arr, int k, int startIndex, List<Integer> combineList, List<List<Integer>> res) {
        if (k == combineList.size()) {
            res.add(new ArrayList<>(combineList));
        } else {
            for (int i = startIndex; i <= arr.length - (k - combineList.size()); i++) {
                combineList.add(arr[i]);
                // 注意 startIndex = i + 1，是因为递归的过程中，不能再次选择 i+1 前面的元素
                dfs(arr, k, i + 1, combineList, res);
                combineList.remove(combineList.size() - 1);
            }
        }
    }

    static void removeInValidRes(Set<String> possibleRes) {
        possibleRes.removeIf(res -> {
            Deque<Character> deque = new LinkedList<>();
            for (char c : res.toCharArray()) {
                // 括号才进行处理
                if (c == '(' || c == ')') {
                    if (c == '(') {
                        deque.addLast('(');
                    } else {
                        // deque为空，且进来 ')' 则要移除
                        if (deque.isEmpty()) {
                            return true;
                        } else {
                            deque.removeLast();
                        }
                    }
                }
            }
            // 不用移除
            return false;
        });
    }

}
